package com.aug_leo.datastructure.linkedlist;

/**
 * 根据值删除节点
 */
public class E02Leetcode203 {

    /**
     * <h3>方法一</h3>
     *
     * 图中 s 代表 sentinel哨兵（如果不加哨兵，则删除第一个节点要特殊处理），例如要删除6<br>
     * p1   p2
     * s -> 1 -> 2 -> 6 -> 3 -> 6 -> null
     *
     * <p>如果p2不等于目标，则p1，p2不断后移</p>
     *
     *      p1   p2
     * s -> 1 -> 2 -> 6 -> 3 -> 6 -> null
     * <br>
     *           p1   p2
     * s -> 1 -> 2 -> 6 -> 3 -> 6 -> null
     *
     * <p>p2==6，删除它，注意p1此时保持不变</p>
     *           p1   p2
     * s -> 1 -> 2 -> 3 -> 6 -> null
     *
     * <p>p2不等于目标，则p1，p2不断后移</p>
     *                p1   p2
     * s -> 1 -> 2 -> 3 -> 6 -> null
     *
     * <p>p2 == 6，删除它，注意p2此时保持不变</p>
     *                p1   p2
     * s -> 1 -> 2 -> 3 -> null
     *
     * <p>p2 == null 退出循环</p>
     * @param head 链表头
     * @param value  目标值
     * @return 删除后的链表头
     */
    public ListNode removeElements1(ListNode head, int value) {
        ListNode sentinel = new ListNode(-1, head); // 哨兵节点
        ListNode pointer1 = sentinel;
        ListNode pointer2 = sentinel.next;
        while (pointer2 != null) {
            if (pointer2.val == value) {
                // 删除，pointer2向后平移
                pointer1.next = pointer2.next;
                pointer2 = pointer2.next;
            } else {
                // pointer1 pointer2 向后平移
                pointer1 = pointer1.next;
                pointer2 = pointer2.next;
            }
        }
        return sentinel.next;
    }

    // 改动简化版
    public ListNode removeElements(ListNode head, int value) {
        ListNode sentinel = new ListNode(-1, head); // 哨兵节点
        ListNode pointer1 = sentinel;
        ListNode pointer2;
        while ((pointer2 = pointer1.next) != null) {
            if (pointer2.val == value) {
                // 删除，pointer2向后平移
                pointer1.next = pointer2.next;
            } else {
                // pointer1 pointer2 向后平移
                pointer1 = pointer1.next;
            }
        }
        return sentinel.next;
    }

    /**
     * <h3>方法二</h3>
     * 思路: 递归函数负责返回：从当前节点（我）开始，完成删除的子链表
     * 1. 若我与 v 相等，应该返回下一个节点递归结果
     * 2. 若我与 v 不等，应该返回我，但我的 next 应该更新（让我能带上后续删过的子链表）
     * @param pointer   链表头
     * @param val 目标值
     * @return 删除后的链表头
     */
    public ListNode removeElements2(ListNode pointer, int val) {
        if (pointer == null) {
            return null;
        }
        if (pointer.val == val) {
            return removeElements(pointer.next, val);
        } else {
            pointer.next = removeElements(pointer.next, val);
            return pointer;
        }
    }

    public static void main(String[] args) {
        ListNode head = ListNode.of(1, 2, 6, 3, 6);
//        ListNode head = ListNode.of(7, 7, 7, 7);
        System.out.println(head);
        System.out.println(new E02Leetcode203()
                .removeElements2(head, 6));
    }
}
